\documentclass{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
% \usepackage{ctex}
\usepackage{listings}
\usepackage{subfigure}
\usepackage{setspace}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}

\usepackage{xcolor}
\usepackage{fontspec} 
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{comment}{rgb}{0.56,0.64,0.68}

\newfontfamily\monaco{Monaco}
\lstset {
aboveskip=3mm,
belowskip=3mm,
showstringspaces=false,       % underline spaces within strings
columns=flexible,
framerule=1pt,
rulecolor=\color{gray!35},
backgroundcolor=\color{gray!5},
basicstyle={\small\monaco},           % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\tiny\monaco\color{gray},  % the style that is used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
commentstyle=\color{comment},
keywordstyle=\color{blue},
stringstyle=\color{dkgreen},
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
escapeinside={\%*}{*)},            % if add LaTeX within your code
morekeywords={*,...}               % if add more keywords to the set
}


\begin{document}
\title{Homework \#2}
\pagestyle{fancy}
\lhead{Name Li HuiTeng 3180102114}
\chead{ NumAnalysis\#2}
\rhead{Date 21.10.19}

\section{Theoretical questions}

\RNum{1}.
\begin{proof}
  Since it's a linear interpolation with $f(1)=1,f(2)=\frac{1}{2}$, we have
  \begin{align*}
    p_1(f;x)=-\frac{1}{2}x+\frac{3}{2}.
  \end{align*}
  Also, $f''(x)=\frac{2}{x^3}$ yields
  \begin{align*}
    \frac{2}{2\xi(x)^3}(x-1)(x-2)&=\frac{1}{x}-(-\frac{1}{2}x+\frac{3}{2}),\\
    \xi(x)&=(2x)^{\frac{1}{3}}.
  \end{align*}
  Then we have
  \begin{align*}
    max\xi(x)&=\xi(2)=4^{\frac{1}{3}},\\
    min\xi(x)&=\xi(1)=2^{\frac{1}{3}},\\
    maxf''(\xi(x))&=\frac{2}{(min\xi(x))^3}=1.
  \end{align*}
\end{proof}

\RNum{2}.
\begin{proof}
  To interpolate given values $\sqrt{f_0},\sqrt{f_1},\cdots,\sqrt{f_n}$ at distinct points 
  $x_0,x_1,\cdots,x_n$, we apply the Lagrange formula, which yields
  \begin{align*}
    p_n(x)=\sum\limits_{k=0}^{n}\sqrt{f_k}l_k(x),
  \end{align*}
  where $deg(p_n(x))\leq n$ and $l_k(x)$ is the fundamental polynomial for pointwise interpolation. 
  
  Define $p(x):=p_n(x)^2=(\sum\limits_{k=0}^{n}\sqrt{f_k}l_k(x))^2$. Then $p(x) \in P^+_{2n}$ and $p(x_i)=p_n(x_i)^2=f_i$ for $i=0,1,\cdots,n$, 
  which satisfy our demands. 
\end{proof}

\RNum{3}.
\begin{proof}
  The proof is by mathematical induction on n. 
  The result is immediate if $n=0$.
  Assume that for some integer $n \geq 0$, $f[t,t+1,\cdots,t+n]=\frac{(e-1)^n}{n!}e^t.$

  Then combining it with (3.17), we have 
  \begin{align*}
    f[t,t+1,\cdots,t+n+1]&=\frac{f[t+1,\cdots,t+n+1]-f[t,\cdots,n]}{t+n+1-t}\\
    &=\frac{\frac{(e-1)^n}{n!}e^{t+1}-\frac{(e-1)^n}{n!}e^t}{n+1}\\
    &=\frac{(e-1)^{n+1}}{(n+1)!}e^t.
  \end{align*}
  This shows the theorem is true for $n+1$, and so the theorem is true for all $n\in N$ 
  by mathematical induction.

  Combine the theorem with Corollary 3.22 and let $t=0$. We have
  \begin{align*}
    \frac{1}{n!}f^{(n)}(\xi_n)&=f[0,1,\cdots,n]=\frac{(e-1)^n}{n!},\\
    f^{(n)}(\xi_n)&=(e-1)^n,\\
    \xi_n&=(ln(e-1))*n.
  \end{align*} 
  Since $ln(e-1)>0.54132$, $\xi$ is located to the right of the midpoint n/2.
\end{proof}
\newpage
\RNum{4}.
\begin{proof}
By definition 3.18, we can construct the following table of divided difference,

\begin{table}[!htbp]
  \centering
  \begin{tabular}{l|llll}
  0 & 5  &    &     &       \\
  1 & 3  & -2 &     &       \\
  3 & 5  & 1  & 1   &       \\
  4 & 12 & 7  & 2   & 1/4
  \end{tabular}
\end{table}

By definition 3.14, the interpolating polynomial is generated from the main diagonal 
and the first column of the above table as follows.
\begin{align*}
  p_3&=5-2x+x(x-1)+\frac{1}{4}x(x-1)(x-3)
\end{align*}
Then
\begin{align*}
p_3'(x)&=-2+2x-1+\frac{1}{4}(3x^2-8x+3)=\frac{3x^2-9}{4}.\\
\end{align*}
Hence $p_3(x \in(1,3))$ reaches its minimum at $\sqrt{3}$ and $x_{min}=\sqrt{3}$.  
\end{proof}

\RNum{5}.
\begin{proof}
By definition 3.18 and 3.32, we can construct the following table of divided difference,\\
\begin{table}[!htbp]
      \centering
      \begin{tabular}{l|llllll}
      0 & 0   &     &     &     &     &    \\
      1 & 1   & 1   &     &     &     &    \\
      1 & 1   & 7   & 6   &     &     &    \\
      1 & 1   & 7   & 21  & 15  &     &    \\
      2 & 128 & 127 & 120 & 99  & 42  &    \\
      2 & 128 & 448 & 321 & 201 & 102 & 30
      \end{tabular}
\end{table}
Hence, $f[0,1,1,1,2,2]=30$.\\
Then we have 
\begin{align*}
  \frac{f^{5}(\xi)}{5!}=30\Rightarrow
  \frac{7!/2}{5!}\xi^2&=30,\\
  \xi &= \sqrt{\frac{10}{7}} ,\xi \in (0,2). 
\end{align*}
\end{proof}

\RNum{6}
\begin{proof}
By definition 3.18 and 3.32, we can construct the following table of divided difference,\\
  \begin{table}[!htbp]
    \centering
    \begin{tabular}{l|lllll}
    0 & 1 &    &     &     &       \\
    1 & 2 & 1  &     &     &       \\
    1 & 2 & -1 & -2  &     &       \\
    3 & 0 & -1 & 0   & 2/3 &       \\
    3 & 0 & 0  & 1/2 & 1/4 & -5/36
    \end{tabular}
    \end{table}

Then 
\begin{align*}
p=1+x-2x(x-1)+\frac{2}{3}x(x-1)^2-\frac{5}{36}x(x-1)^2(x-3), \quad
f_{rough}(2)=p(2)=\frac{11}{18}.
\end{align*}

By Theorem 3.33, we have 
\[
f(x)-p(x)=\frac{f^{(5)}(\xi)}{5!}x(x-1)^2(x-3)^2, 
\]
where $\xi \in (0,3)$. Then define $h(x):=x(x-1)^2(x-3)^2$, and we have\\
$h'(x)=(x-1)(x-3)(5x^2-12x+3)=(x-r_1)(x-1)(x-r_2)(x-3)$, $r_1=\frac{6-\sqrt{21}}{5}\in(0,0.5)$, $r_2=\frac{6+\sqrt{21}}{5}\in(2,2.5)$ .\\
Since $|h(x)|$ reaches its maximum on extreme points or end points, and
\begin{align*}
  h(0)=0,\quad
  h(r_1)=1.074001461,\quad
  h(1)=0,\quad
  h(r_2)=2.059438539, \quad
  h(3)=0,
\end{align*}
we have maximum possible error is bounded by $\frac{1}{120}h(r_2)M$. 
\end{proof}

\RNum{7}
\begin{proof}
  For forward difference, the proof is by mathematical induction on k. 
  The result is immediate if $k=1$, since $\frac{\Delta f(x)}{h}=\frac{f(x_1)-f(x_0)}{h}=f[x_0,x_1]$.\\
  Assume that for some integer $k \geq 1$, $\Delta^k f(x)=k!h^kf[x_0,\cdots,x_k]$.\\
  Then combining it with (3.17), we have
  \begin{align*}
    \Delta^{k+1} f(x)=\Delta^k f(x+h)-\Delta^k f(x)&=k!h^k(f[x_1,\cdots,x_{k+1}]-f[x_0,\cdots,x_{k}])\\
    &=k!h^k(x_{k+1}-x_0)f[x_0,\cdots,x_{k+1}]\\
    &=(k+1)!h^{k+1}f[x_0,\cdots,x_{k+1}].
  \end{align*}
  This shows the theorem is true for $k+1$, and so the theorem is true for all $k\in N^+$ 
  by mathematical induction.\\
  For backward difference, the proof makes no difference.
\end{proof}

\RNum{8}
\begin{proof}
  The proof is by mathematical induction on n.
  If $n=1$, we have 
  \begin{align*}
    \difFrac{}{x_0}f[x_0,x_1]&=\frac{f'(x_0)(x_0-x_1)-(f(x_0)-f(x_1))}{(x_0-x_1)^2},\\
    f[x_0,x_0,x_1]&=\frac{f[x_0,x_0]-f[x_0,x_1]}{x_0-x_1}=\frac{f'(x_0)-\frac{f(x_0)-f(x_1)}{x_0-x_1}}{x_0-x_1}.
  \end{align*}
  Hence the result is immediate. Assume that for some integer $n \geq 1$, 
  $\difFrac{}{x_0}f[x_0,\cdots,x_n]=f[x_0,x_0,x_1,\cdots,x_n]$.\\
  Then 
  \begin{align*}
    \difFrac{}{x_0}f[x_0,\cdots,x_n,x_{n+1}]&=\difFrac{}{x_0}\frac{f[x_0,\cdots,x_n]-f[x_1,\cdots,x_{n+1}]}{x_0-x_{n+1}}\\
    &=\frac{f[x_0,x_0,\cdots,x_n](x_0-x_{n+1})-(f[x_0,\cdots,x_n]-f[x_1,\cdots,x_{n+1}])}{(x_0-x_{n+1})^2}\\
    &=\frac{f[x_0,x_0,\cdots,x_n]-\frac{f[x_0,\cdots,x_n]-f[x_1,\cdots,x_{n+1}]}{x_0-x_{n+1}}}{x_0-x_{n+1}}\\
    &=\frac{f[x_0,x_0,\cdots,x_n]-f[x_0,\cdots,x_n,x_{n+1}]}{x_0-x_{n+1}}\\
    &=f[x_0,x_0,\cdots,x_n,x_{n+1}].
  \end{align*}
  This shows the theorem is true for $n+1$, and so the theorem is true for all $n\in N^+$ 
  by mathematical induction.\\
  Similarly, assuming $f$ is differentiable at $x_k$, then $\difFrac{}{x_k}f[x_0,\cdots,x_n]=f[x_0,\cdots,x_n,x_k]$, where $k=0,1,\cdots,n$.
\end{proof}

\RNum{9}
\begin{proof}
  Define 
  $\lambda (t) = \frac{b+a}{2}+\frac{b-a}{2}t$ and set $t$, s.t. $\lambda(t)=x$. Then  
  \begin{align*}
    \min\max\limits_{x\in[a,b]}|a_0x^n+a_1x^{n-1}+\cdots+a_n|&=\min\max\limits_{t\in[-1,1]}|a_0(\lambda(t))^n+a_1(\lambda(t))^{n-1}+\cdots+a_n|\\
    &=|a_0|\min\max\limits_{t\in[-1,1]}|(\frac{b+a}{2}+\frac{b-a}{2}t)^n+b_1(\lambda(t))^{n-1}+\cdots+b_n|\\
    &=|a_0|\frac{(b-a)^n}{2^n}\min\max\limits_{t\in[-1,1]}|t^n+c_1t^{n-1}+\cdots+c_n|\\
    &=|a_0|\frac{(b-a)^n}{2^{2n-1}},
  \end{align*}
  where the last step follows from Corollary (3.45) from ChebyShev Theorem.
\end{proof}

\RNum{10}
\begin{proof}
  $\tilde{p}_n(x)$ assumes its extrema n+1 times at the points $x'_k$, and $T_n(a)>0$ since $T_n(x)$ is monotonically increasing on $x \in [1,\infty)$ and $a>1$, $T_n(1)=1$.\\
  Suppose $||\tilde{p}_n(x) ||_{\infty}\leq ||p||_{\infty}$ does not hold. Then Theorem 3.38 implies that 
  \begin{align*}
  \exists p \in P^a_n   \text{ s.t. }   ||p(x) ||_{\infty}<\frac{1}{T_n(a)}.
  \end{align*}
  Consider the polynomial $Q(x)=\frac{1}{T_n(a)}T_n(x)-p(x)$.   
  $
    Q(x'_k)=\frac{(-1)^k}{T_n(a)}-p(x'_k),\quad k=0,1,\cdots,n.
  $
  Hence $Q(x)$ has alternating signs at these $n+1$ points and $Q(x)$ should have at least $n$ zeros on $[-1,1]$. 
  However, by the construction of $Q(x)$, $Q(a)=0(a>1)$ and $deg(Q(x))\leq n$. Therefore, $Q(x)\equiv 0$ and $p(x)=\frac{T_n(x)}{T_n(a)}$, which 
  implies $ ||p(x) ||_{\infty}=\frac{1}{T_n(a)}$. This is a contradiction to the suppose.
\end{proof}


\section{C++ programming}
Use $ \textbf{make all} $ to generate all answers! \\ 
Codes are contained in the e-mail tar, and only conclusions will be shown in the following part.\\
Results are shown below, generating from $ \textbf{make run} $.
\lstset{language=Matlab}
\begin{lstlisting}
  g++ -o Assignment.o Assignment.cpp
  ./Assignment.o
  -----------------------Assignment B-----------------------
  px = -0.0384615*x.^2 +1*x.^0 
  px = 0.00530504*x.^4 -0.171088*x.^2 +1*x.^0 
  px = -0.000840633*x.^6 +0.0335319*x.^4 -0.351364*x.^2 +1*x.^0 
  px = 0.000137445*x.^8 -0.00658016*x.^6 +0.0981875*x.^4 -0.528121*x.^2 +1*x.^0 
  Generate AssignmentB.m!
  -----------------------Assignment C-----------------------
  px = 2.7465*x.^4 -3.54298*x.^2 +1*x.^0 
  px = 5.51277*x.^8 -14.0024*x.^6 +12.6193*x.^4 -4.81162*x.^2 +0.730822*x.^0 
  px = -333.619*x.^14 +1264.42*x.^12 -1927.18*x.^10 +1510.61*x.^8 -646.864*x.^6 +149.027*x.^4 -17.3641*x.^2 +1*x.^0 
  px = -788.326*x.^18 +3973.16*x.^16 -8534.89*x.^14 +10195.5*x.^12 -7413.45*x.^10 +3379.02*x.^8 -960.825*x.^6 +165.458*x.^4 -16.5422*x.^2 +0.96241*x.^0 
  Generate AssignmentC.m!
  -----------------------Assignment D-----------------------
  px = -2.02236e-05*x.^9 +0.00104059*x.^8 -0.0218757*x.^7 +0.243041*x.^6 -1.5383*x.^5 +5.50812*x.^4 -10.0953*x.^3 +7.16191*x.^2 +75*x.^1 
  The derivation of px = -0.000182013*x.^8 +0.00832472*x.^7 -0.15313*x.^6 +1.45825*x.^5 -7.69148*x.^4 +22.0325*x.^3 -30.2859*x.^2 +14.3238*x.^1 +75*x.^0 
  (a) When t = 10, 
  Position: 742.503 feet from Time 0.
  Speed: 48.3817 feet per second.
  (b) For t from 0 to 13, 
  the car exceeds the speed limit when t = 5.93 .
  -----------------------Assignment E-----------------------
  px = 4.1477e-05*x.^6 -0.00371557*x.^5 +0.128281*x.^4 -2.11512*x.^3 +16.2855*x.^2 -43.0127*x.^1 +6.67*x.^0 
  px = 8.6768e-06*x.^6 -0.000777473*x.^5 +0.0265858*x.^4 -0.424283*x.^3 +2.98227*x.^2 -5.85018*x.^1 +6.67*x.^0 
  Generate AssignmentE.m !  
\end{lstlisting}

For AssignmentE, we can see from plotting that both two samples of larvae will survive after 15 days.

Picture results are shown below, generating from $ \textbf{make plot} $.
\newpage
\includegraphics[width=0.8\textwidth]{AssignmentB.png}

\includegraphics[width=0.8\textwidth]{AssignmentC.png}

\includegraphics[width=0.8\textwidth]{AssignmentE1.png}

\includegraphics[width=0.8\textwidth]{AssignmentE2.png}


\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
